Shtetl-Optimized

An anonymous commenter on my last post asks:

isn’t the real problem with complexity theory that the resulting mathematics is usually superficial and shallow?

does this make it less fun to do complexity theory?

are complexity theorists ever saying something deep?

Later, the same commenter writes:

i’m just curious because I don’t really understand how I feel about the issue myself.

maybe we should start with something more basic. can we all agree that “logic” (i.e. foundations of math) is pretty boring and flavorless?

sure, we all got that little rush when we heard the story of the “fall of mathematics” in the early 20th century … and then maybe again with the axiom of choice, continuum hypothesis, independence, forcing, and various incompleteness theorems.

but is logic actually fun to do? on an emotional level, do you achieve understanding, intuition?

Alright, look, anonymous. You’ve nailed why I don’t work on logic myself — besides not understanding what the big, meaty open problems are. For me, frankly, reading about logic (or recursion theory, or programming language semantics, or distributed computing) has always felt like sipping broth. Sure, it might be delicious broth. In the case of (say) Gödel and Cohen’s independence results, it might even be the best broth I’ve ever tasted. But eventually I hanker for some noodles, some carrots, maybe some complex numbers or a Cauchy-Schwarz inequality. I mean, how long can a person go without bounding anything?

But you see, anonymous, that’s what I like about complexity. It packs the same theological punch as logic does, but it’s got math in it too. And I’m not just talking combinatorics and graph theory. Let me put it to you this way:

You like groups? We got groups.

You like vector spaces? We got them too.

But what about number theory? Finite fields? Fourier transforms? Continued fractions? “Shor.”

Eigenvalues? Chebyshev polynomials? Gaussians? Random walks? Lattices? Convex polytopes? Banach spaces? Metric embeddings? You better believe it.

Or how about this, anonymous: what’s your favorite constant? π? e? The golden mean? Maybe 0.288…=(1/2)(3/4)(7/8)(15/16)…? Becoming a complexity theorist doesn’t mean bidding any of them goodbye.

Look, we even got knots, braids, manifolds, unitary representations, varieties, cohomologies, plethysms — alright, maybe not so much of the last few. But if your favorite mathematical object isn’t in stock, bring it yourself! That’s the thing about complexity: anything is fair game if it yields a new upper or lower bound. The reason it’s so hard to prove P!=NP is precisely that a fast SAT algorithm could be hiding anywhere in the math library.

Now let me turn the tables, anonymous. Can you name a subfield of math that involves so many different kinds of math?

Follow

If a layperson asks you what computational complexity is, you could do worse than to tell the following story, which I learned from Steven Rudich.

A man with a flowing gray beard is standing on a street corner, claiming to be God. A bemused crowd gathers around him. “Prove it!” they taunt.

“Well,” says the man,”I can beat anyone at chess.”

A game is duly arranged against Kasparov, who happens to be in town. The man with the gray beard wins.

“OK, so you’re pretty good at chess,” the onlookers concede. “But that still doesn’t mean you’re God.”

“O ye of little faith! As long as I play White, it’s not just hard to beat me — it’s mathematically impossible! Play Black over and over, try every possible sequence of moves, and you’ll see: I always win.”

A nerd pipes up. “But there are more sequences of moves than there are atoms in the universe! Even supposing you beat us every day for a century, we’d still have no idea whether some sequence of moves we hadn’t tried yet would lead to your defeat. We’ll be long dead before every possibility is examined. So unless you’re prepared to grant us immortality, there’s no way you can possibly convince us!”

Most of you know the punchline to this story, but for those who don’t: the nerd is wrong. By asking a short sequence of randomly-chosen questions, each a followup to the last, the crowd can quickly convince itself, to as high a confidence as it likes, that the man they’re interrogating knows a winning strategy for White — or else expose his lie if he doesn’t. The reason was discovered in 1990 by Lund, Fortnow, Karloff, Nisan, and Shamir, and has less to do with chess than with the zeroes of polynomials over finite fields.

There are two lessons I’d like to draw from Rudich’s Fable of the Chessmaster.

The first lesson is that computational complexity theory is really, really, really not about computers. Computers play the same role in complexity that clocks, trains, and elevators play in relativity. They’re a great way to illustrate the point, they were probably essential for discovering the point, but they’re not the point.

The best definition of complexity theory I can think of is that it’s quantitative theology: the mathematical study of hypothetical superintelligent beings such as gods. Its concerns include:

• If a God or gods existed, how could they reveal themselves to mortals? (IP=PSPACE, or MIP=NEXP in the polytheistic case.)

• Which gods are mightier than which other gods? (P^NP vs. PP, SZK vs. QMA, BQP^NP vs. NP^BQP, etc. etc.)

• Could a munificent God choose to bestow His omniscience on a mortal? (EXP vs. P/poly.)

• Can oracles be trusted? (Can oracles be trusted?)

And of course:

• Could mortals ever become godlike themselves? (P vs. NP, BQP vs. NP.)

Incidentally, it’s ironic that some people derisively refer to string theory as “recreational mathematical theology.” String theory has to earn the status of mathematical theology — right now it’s merely physics! A good place for string theorists to start their theological training is this recent paper by Denef and Douglas.

So that was my first lesson. The second lesson is that interaction helps: you can get your message across a lot faster if people are continually challenging you. If the gray-bearded man were just lecturing to a passive audience, rather than being grilled by doubters trying to trap him in a contradiction, then it would take longer than the age of the universe for him to prove his unbeatability at chess. Or rather, we theologians conjecture that it would.

I’m reminded of the power of interaction every time I give a talk. Despite a certain reputation for cheap yuks, I’ve never been a good speaker. I’m terrible at explaining anything coherently — that is, in a way that anticipates people’s objections. Fortunately, as long as people interrupt me, it doesn’t matter much, since I can easily answer the objections once I know what they are. Indeed, not only do interruptions clue me in on what’s bugging people — as in the Fable of the Chessmaster, they also let me prove that I basically know what I’m talking about, even if I can’t articulate it in the allotted time!

(In my ideal talk, I would begin by saying “Thank you. Are there any questions?”)

For another example, take the sex columnist Dan Savage. Savage has a “philosophy,” which consists partly of a refusal to condemn sex acts if they don’t harm anyone, and a willingness to condemn them if they do. But if he tried to state his philosophy explicitly, he wouldn’t do it justice any more than I just did. So instead he answers questions about used underwear fetishes and masturbating parakeets.

The same goes for comedians, at least the good ones like Jon Stewart. Stewart has an enviably easy job: news happens, he reacts to it. It’s like my ideal talk that consists entirely of questions — except that instead of questions, there’s Bush warning about “human-animal hybrids” in his State of the Union address, or Cheney shooting his hunting buddy in the face.

Inspired by such examples, and by my recent positive experience answering Peter Brooke’s question, I’ve decided to open this blog to questions on a regular basis. Email them, post them in the comments section, whatever. I can’t promise to take up everything. Try to guess which of the following would have a better chance:

“Please discuss the relative merits of conference and journal publication in theoretical computer science.”
“How could schools be redesigned to improve the sex lives of nerds?”

Follow

As winner of the Best Umeshism Contest (remember that?), Peter Brooke earned the right to ask me any question and have me answer it on this blog. Without further ado, here is Peter’s question:

If it is assumed that God exists, what further, reasonable, conclusions can be made, or is that where logical inquiry must end? Reasonable means in the light and inclusive of present scientific understanding. Defend any assumptions and conclusions you make.

At least Peter was kind enough not to spring “Is there a God?” on me. Instead, like a true complexity theorist, he asks what consequences follow if God’s existence is assumed.

Alas, Peter didn’t say which God he has in mind. If it were Allah, or Adonai, or Zeus, or the Flying Spaghetti Monster, then I’d simply refer Peter to the requisite book (or in the case of the Spaghetti Monster, website) and be done. As it is, though, I can’t assume anything about God, except that

1. He exists,
2. He created the universe (if He didn’t, then it’s not He we’re talking about), and
3. He’s a He.

(Note for Miss HT Psych: the third assumption is a joke.)

So the only way I see to proceed is to start from known facts, and then ask what sort of God would be compatible with those facts. Though others might make different choices, the following facts seem particularly relevant to me.

• About 700,000 children each year die of malaria, which can easily be prevented by such means as mosquito nets and the spraying of DDT. That number will almost certainly grow as global warming increases the mosquitoes’ range. As with most diseases, praying to God doesn’t seem to lower one’s susceptibility or improve one’s prognosis.

• According to our best theories of the physical world, it’s not enough to talk about the probability of some future event happening. Instead you have to talk about the amplitude, which could be positive, negative, or even complex. To find the probability of a system ending up in some state, first you add the amplitudes for all the ways the system “could” reach that state. Then you take the absolute value of the sum, and lastly you take the square of the absolute value. For example, if a photon could reach a detector one way with amplitude i/2, and another way with amplitude -i/2, then the probability of it reaching the detector is |i/2 + (-i/2)|² = 0. In other words, it never reaches the detector, since the two ways it could have reached it “interfere destructively” and cancel each other out. If we required the amplitudes to be positive or negative reals rather than complex numbers, there would be some subtle differences — for example, we could just square to get probabilities, instead of taking the absolute value first. But in most respects the story would be the same.

• From 1942 to 1945, over a million men, women, and children died in one of four extermination complexes at Birkenau, or “Auschwitz II” (Auschwitz I was the smaller labor camp). Each complex could process about 2,500 prisoners at a time. The prisoners were ordered to strip and leave their belongings in a place where they could find them later. They were then led to an adjacent “shower room,” containing shower heads that were never connected to any water supply. Once they were locked inside, guards dropped pellets from small openings in the ceiling or walls. The pellets contained Zyklon B, a cyanide-based nerve agent invented in the 1920’s by the German Jewish chemist Fritz Haber. The guards then waited for the screams to stop, which took 3-15 minutes, depending on humidity and other factors. Finally, Sonderkommandos (prisoners who were sent to the gas chambers themselves at regular intervals) disposed of the bodies in the adjacent crematoria. With the arrival of 438,000 Hungarian Jews in 1944, the crematoria could no longer keep up, so the bodies were burned in open pits instead. Besides those killed at Auschwitz, another 1.6 million were killed at the four other death camps (Sobibor, Belzec, Treblinka, and Chelmno). In the USSR and Poland, another 1.4 million were shot in front of outdoor pits by the Einsatzgruppen; still others died through forced starvation and other means. Judged on its own terms, the extermination program was a spectacular success: it wiped out at least 2/3 of Russian and European Jewry and changed the demography of Europe. The Americans and British declined numerous opportunities to take in refugees, or to bomb the camps or the train tracks leading to them. Most of the perpetrators, except for a few top ones, returned to civilian life afterward and never faced trial. Millions of people today remain committed to the goal of a Judenrein planet; some, like my friend Mahmoud, are working to acquire nuclear weapons.

• According to our best description of space and time, the faster an object is moving relative to you, the shorter that object will look in its direction of motion, and the slower time will pass for it as observed by you. In particular, if the object is moving at a fraction f of the speed of light, then it will contract, and time will slow down for it, by a factor of 1/(1-f²)^1/2. This does not mean, as some people think, that concepts like “distance” have no observer-independent meaning — only that we were using the wrong definition of distance. In particular, suppose an observer judges two events to happen r light-years apart in space and t years apart in time. Then the interval between the events, defined as r²-t², is something that all other observers will agree on, even they disagree about r and t themselves. The interval can also be defined as r²+(it)²: in other words, as the squared Euclidean distance in spacetime between the events, provided we reinterpret time as an imaginary coordinate. (This is known as “Wick rotation.”)

• When I was younger, my brother and I went to an orthodontist named Jon Kraut. Dr. Kraut was a jovial guy, who often saw me on weekends when I was home from college even though his office was officially closed. He was also an aviation enthusiast and licensed pilot. About a week ago, Kraut was flying a twin-engine plane to South Carolina with his wife, Robin, their three kids (ages 2, 6, and 8), and the kids’ babysitter. Kraut reported to the control tower that he was having problems with his left engine. The plane made one approach to the airport and was coming back to try to land again when it crashed short of the runway, killing the whole family along with the babysitter. On the scale of history, this wasn’t a remarkable event; I only mention it because I knew and liked some of the victims.

Now, based on the facts above, plus many others I didn’t mention, and “in the light … of present scientific understanding,” what can we say about God, assuming He exists? I think we can say the following.

First, that He’s created Himself a vale of tears, a theater of misery beyond the imagination of any horror writer. That He’s either unaware of all the undeserved suffering He’s wrought, or else unable or unwilling to prevent it. That in times of greatest need, He’s nowhere to be found. That He doesn’t answer the prayers of the afflicted, or punish evildoers in any discernible way. That He most likely doesn’t intervene in human affairs at all — though I wouldn’t want to argue with those who say He does intervene, but only for the worse.

Second, that He apparently prefers complex numbers to real numbers, and the L₂ norm to the L₁ norm.

Follow

Over at Not Even Wrong, Peter Woit pans “Down the Rabbit Hole,” a movie about quantum mechanics, paranormal phenomena, and the deep imaginary connection between the two that’s setting the pseudoscience world on fire. (Don’t worry — the fire is harmless to those who have balanced their chakras.)

“Rabbit Hole” is a rehash of the 2004 film “What the Bleep Do We Know!?”; apparently the new version is longer and includes more crackpots, but the basic howlers are the same. (Woit’s summary: “entanglement=we are all connected, superposition=anything you want to be true is true.”)

I suppose I’ll eventually have to don a fake mustache, clothespin my nose, and go endure this movie, since people often bring it up when I tell them what I do for a living:

ME: …so, at least in the black-box model that we can analyze, my result implies that the quantum speedup for breaking cryptographic hash functions is only a polynomial one, as opposed to the exponential speedup of Shor’s factoring algorithm.

PERSON AT COCKTAIL PARTY: How interesting! It’s just like they were saying in the movie: reality is merely a construct of our minds.

But if I do jump down the Rabbit Hole, my worry is that I won’t make it through:

“Sir, if you don’t stop causing a disturbance, we’ll have to escort you out of the movie theater…”

“BUT YOU CAN’T USE QUANTUM MECHANICS TO CHANNEL DEAD PEOPLE! IT’S A LINEAR THEORY! POSTSELECTION’S NOT ALLOWED!”

“Alright, come with us, sir.”

“LINEAR, I TELL YOU! AND THE MEASUREMENTS OBEY THE |Ψ|² RULE! WHAT THE %*#()$*$ DO THESE IDIOTS KNOW!? I’M BEGGING YOU, STOP THE PROJECTOR!”

Since this hasn’t yet happened, what inspired the present post was not the movie itself, but its title graphic:

Staring at this image, I came up with something that I call the Cringeometer: a quick way for anyone, scientist or not, to predict whether a given popular depiction of science will cause scientists to cringe. To use the Cringeometer, you don’t have to make any decisions about technical accuracy. All you have to do is look for mathematical symbols such as Σ, ε, and π, and then ask yourself two questions:

1. Are the symbols used to create an aura of profundity and unintelligibility, without regard for their meaning — more or less like Christmas tree ornaments?
2. If so, is the effect humorous?

The results should be self-explanatory — but just in case they aren’t, I’ll end with three sample applications of the Cringeometer.

• “What the Bleep?” explodes the Cringeometer even before the movie has started.

• NUMB3RS also sets the Cringeometer off, even though it probably does more good than harm for public math appreciation. This illustrates that the Cringeometer can’t predict scientists’ detailed opinions — only the involuntary, physical reaction of cringing.

• “The Far Side” cartoons never set the Cringeometer off.

Follow

My car battery died. My latest research languishes half-written on my hard drive. My receipts for travel reimbursement lie unsubmitted on my floor. My academic future is yet to be decided. So what better way to spend an afternoon than by browsing the SPAM Haiku Archive, and compiling the 62 finest exemplars of the genre into this file?

If you’re sitting in a shared office, or are drinking a beverage such as milk, please click at your own risk. The yuks-to-syllable ratio is one of the highest I’ve seen in months, and I’ve never even tasted the stuff.

Follow

The list of accepted papers for STOC’06 is now available. The process of forming this list confirmed my fundamental respect for the scientific peer review process — a process that, in its speed, objectivity, and reliance on reasoned argument, might someday rival such renowned deliberative bodies as the US House of Representatives.

For this experience I’m deeply grateful to my 19 fellow program committee members, except of course when they mistakenly disagreed with me. I’m especially grateful to Jon Kleinberg, the PC chair, for inviting me to join the committee, even though he only gave me an A- in his COMS681 Analysis of Algorithms class my freshman year at Cornell. Finally I feel like I’ve made it.

I’d love to tell you all about the heated debates, shifting alliances, and last-minute turnarounds that characterized our committee meeting in the moonlit Fortress of STOC — until we, clad in hooded robes, brandishing our laptops as torches, and calling on NEXP and PSPACE for benediction, sealed the minutes of our deliberations in the sacred Vault of Turing, which no one without a PhD in a technical subject can gaze upon and live, and which can only be opened if all twenty of us come together with twenty golden keys. (We thought of using encryption, but it seemed too complicated and theoretical.)

Yes, I’d love to tell you about it, but I’d have to kill you afterwards, and then who would be left to read my blog?

Follow

Genocide. Global warming. Nuclear proliferation. Sex trafficking in Cambodia. Famine in sub-Saharan Africa.

If history has taught us anything, it’s that problems like these tend to sort themselves out if we just ignore them for long enough. So I get annoyed when guys like Nicholas Kristof keep reminding people about them, thereby diverting attention from real issues like steroid abuse in the NFL.

In his latest piece of “offbeat” journalism, Kristof pulls out the stops, explicitly comparing humankind’s current failure to prevent the Darfur genocide with its failure to prevent earlier genocides:

During the Holocaust, the world looked the other way. Allied leaders turned down repeated pleas to bomb the Nazi extermination camps or the rail lines leading to them, and the slaughter attracted little attention. My newspaper, The New York Times, provided meticulous coverage of World War II, but of 24,000 front-page stories published in that period only six referred on page one directly to the Nazi assault on the Jewish population of Europe. Only afterward did many people mourn the death of Anne Frank, construct Holocaust museums, and vow: Never Again.

The same paralysis occurred as Rwandans were being slaughtered in 1994. Officials from Europe to the US to the UN headquarters all responded by temporizing and then, at most, by holding meetings. The only thing President Clinton did for Rwandan genocide victims was issue a magnificent apology after they were dead.

Much the same has been true of the Western response to the Armenian genocide of 1915, the Cambodian genocide of the 1970s, and the Bosnian massacres of the 1990s. In each case, we have wrung our hands afterward and offered the lame excuse that it all happened too fast, or that we didn’t fully comprehend the carnage when it was still under way.

And now — let me guess — the same is happening in Darfur. Arab Janjaweed militias, supported by the Sudanese government, are systemically massacring, raping, and mutilating non-Arab civilians, while the world watches on in horror but does nothing. Dude, what a shocker. I never could have predicted that one.

Think about it. Sixty years after Auschwitz, obviously the world must have solved this genocide thing. The US, or EU, or UN, or someone must have set up some sort of special army that, you know, goes in and stops it before it happens. I mean, anything else would be criminally insane! It would be like 911 putting people on hold for an hour, or a hospital telling a guy spewing arterial blood to sit in the waiting room and read a magazine. Right?

Even if not, I’ve just spent over 20 minutes of valuable procrastination time writing this post and sending some money. So regardless of what happens in Darfur, you can’t accuse me of having sat in my chair and done nothing. No, I sat in my chair and did something.

Follow

“How To Be A Serious Researcher,” my infamous after-dinner speech at QIP’2006, is now available as an mp3 (5MB, 21 minutes). If you want to tar-and-feather me for this, don’t forget Ben Toner (who made the recording) or Julia Kempe (who sent the photo).

Follow

I’ve been told that “the world is awaiting” my report about the QIP’2006 conference. So here it is. I’m in Paris, near the Pantheon. The buildings are beautiful, but the weather is crummy. The food is tasty, expensive, and fattening. Everyone here has been friendly, which is surprising — considering that I’m conspicuously American, and that my French consists almost entirely of the following phrases:

Bonjour!
Merci!
Oui!
Je ne comprends pas!
Monsieur
Madame
École Polytechnique
Croissant
Baguette
Ravioli (no, wait — that’s Italian)

(I’m in a talk right now, using the wireless Internet, and Harry Buhrman is reading this over my shoulder and laughing. Stop that, Harry!)

Oh, right: there have also been talks here. Maybe I’ll blog about them in a later post, but then again, maybe not. I’m not giving a talk, but I am giving the after-dinner speech on Thursday, the quantum computing community having relegated me to the role of jester. Which reminds me that I should write the speech.

I should also apply for jobs for next year. Actually, would anyone like to offer me a tenure-track faculty position right now? Most of the deadlines have passed, and I haven’t even written my research statement — so if that sort of thing doesn’t bother you, your chances of getting me are excellent.

Follow